 1.递归之递归基本思想
   
   递归的基本思想就是拆解问题，通过下图理解递归的思想
   拆分问题
       把规模大的问题编程规模较小的同类型问题
       规模较小的问题又不断变成规模更小的问题
       规模小到一定程度就可以直接得到结果
   求解
       由最小规模问题的解推导出较大规模问题的解
       由较大规模问题的解不断推导出规模更大问题的解
       最后推导出原来问题的解
   总结：
   只要问题符合上述描述也就是可以拆解问题和求解，可以尝试使用递归解决！！
   
 2.递归使用步骤与技巧
   
   1).确定函数的功能
   第一步先不要思考函数里面代码逻辑如何实现，先搞清楚这个函数的目的，完成什么事情？
   2).确定子问题与原问题的关系
   找到 f(n) 与 f(n – 1) 的关系
   f(n)=f(n-1)+n
   3).明确递归基(边界条件)
   递归的过程中，问题的规模在不断减小，当问题缩减到一定程度便可以直接得出它的解
   寻找递归基，等价于：问题规模小到什么程度可以直接得出解？
package com.lg.sum;

/**
 * 计算1到n的累加和
 */
public class SumDemo {

    /**
     * 递归使用步骤
     */
    // 1.先定义一个函数，确定函数的功能(不要考虑函数的实现逻辑)
    // 这个函数的功能就是：计算1到n的累加和
    public static int sum(int n) {
        // 3.确定递归基(边界条件) 小技巧:判断代码的边界条件
        if (n <= 1) {return n;}
        // 2.确定子问题与原问题的解：1到n的累加和与1到n-1的累加和什么关系
        // sum(n) = sum(n-1)+n
        return sum(n-1)+n;
    }

    public static void main(String[] args) {
        System.out.println(sum(3));
    }


}

 3.递归练习之斐波那契数列
   
package com.lg.fib;

/**
 * 斐波那契数列：1、1、2、3、5、8、13、21、34、……
 * F(1)=1，F(2)=1, F(n)=F(n-1)+F(n-2)（n≥3）
 * 编写一个函数求第 n 项斐波那契数
 */

public class FibDemo1 {
	//时间复杂度O(2^n)
    //空间复杂度O(n)
    //函数功能就是计算第n项斐波那契数列的值
    static int fib(int n) {
        if (n<=2){return 1;} //递归基
        return fib(n-1)+fib(n-2);//子问题与原问题的解
    }

    public static void main(String[] args) {
        System.out.println(fib(4));
    }
}

  根据递推式 T n = T (n − 1) + T(n − 2) + O(1)，可得知
      时间复杂度：O(2^n)
      空间复杂度：O(n)
      递归调用的空间复杂度 = 递归深度 * 每次调用所需的辅助空间
  是不是所有递归调用都是O(n)级别的空间复杂度呢？
  先执行左边，左边结束后再执行右边
  递归深度借助调用过程
  1).优化1 (使用数组)  
  时间复杂度高的原因：出现了很多重复计算，可以认为是一种自顶向下的调用过程！！
  优化方案：避免掉重复计算，之前计算过的值不要再次计算！！
  思路：使用数组存放之前的计算结果，正好利用索引！！
package com.lg.fib;

/**
 * 斐波那契数列：1、1、2、3、5、8、13、21、34、……
 * F(1)=1，F(2)=1, F(n)=F(n-1)+F(n-2)（n≥3）
 * 编写一个函数求第 n 项斐波那契数
 */

public class FibDemo2 {
    //函数功能就是计算第n项斐波那契数列的值
    //使用数组优化时间复杂度
    static int fib(int n) {
        //给定一个指定长度的数组
        int[] arr =new int[n+1]; //只是为了数组索引对应fib(n)
        if (n <= 2) {
            return 1;
        }
        //定义递归基
        arr[1]=arr[2]=1;
        return fib1(n, arr) ;//子问题与原问题的解
    }

    //时间复杂度降为O(n)
    //空间复杂度：O(n)
    static int fib1(int n, int[] arr) {
        //使用数组存储已经计算过的数值
        if (arr[n]== 0){
            //数组初始化的值，说明之前没有计算过并存入到数组中
            arr[n]= fib1(n-1, arr) + fib1(n-2, arr);
        }
        return arr[n];
    }

    public static void main(String[] args) {
        Times.test("使用数组优化后斐波那契:O(n)",
                new Times.Task() {
                    public void execute() {
                        System.out.println(fib(60));
                    }
                });
        Times.test("递归方式实现斐波那契:O(2^n)",
                new Times.Task() {
                    public void execute() {
                        System.out.println(FibDemo1.fib(60));
                    }
                });

    }
}
  
  2).优化2(去除递归)
  分析使用数组的调用过程，发现只有第一次的时候需要计算出来，后续其实都无需再计算，同时发现另外一个问题：
  递归调用是自顶向下，如果改为自下向上调用是否可以呢?
  再次理解原问题与子问题的关系
  f(n)=f(n-1)+f(n-2)
  如果先计算出小问题然后再累加求出大问题的解是否可以呢？答案是可以的！！
package com.lg.fib;


/**
 * 斐波那契数列：1、1、2、3、5、8、13、21、34、……
 * F(1)=1，F(2)=1, F(n)=F(n-1)+F(n-2)（n≥3）
 * 编写一个函数求第 n 项斐波那契数
 */

public class FibDemo3 {
    /**
     * 优化思路是变为：原来递归是从上往下计算所以出现了很多重复计算
     * 我们第一版使用了数组记录计算过的值，进行优化(备忘录，记忆化方式)
     * 该为自下向上计算，从小算到大
     */
    // 时间复杂度：O(n)
    // 空间复杂度：O(n)
    static int fib(int n) {
        //给定一个指定长度的数组
        int[] arr = new int[n + 1]; //只是为了数组索引对应fib(n)
        if (n <= 2) {
            return 1;
        }
        //定义递归基
        arr[1] = arr[2] = 1;
        for (int i = 3; i < arr.length; i++) {
            arr[i]=arr[i-1]+arr[i-2];
        }
        return arr[n];
    }

    public static void main(String[] args) {
        System.out.println(fib(3));
    }
}

  3).优化3(借助变量)
  分析第二版代码的计算过程，会发现在计算arr[i]的值时只需要知道前面两个的值即可，其余值已经没有了意义，所
以数组的大部分空间很多时候都是没有意义的！！
  解决方式：去掉数组使用2个变量记录i前面的两个值即可！！
  代码实现
package com.lg.fib;


/**
 * 斐波那契数列：1、1、2、3、5、8、13、21、34、……
 * F(1)=1，F(2)=1, F(n)=F(n-1)+F(n-2)（n≥3）
 * 编写一个函数求第 n 项斐波那契数
 */

public class FibDemo4 {
    /**
     * 优化思路是变为：考虑使用两个变量来替代数组
     */
    // 时间复杂度：O(n)
    // 空间复杂度：O(1)
    static int fib(int n) {
        //给定一个指定长度的数组
        if (n <= 2) {
            return 1;
        }
        /**
         * 定义两个变量替代数组
         */
        int first=1;
        int second=1;
        for (int i = 3; i <=n; i++) {
            second=first+second;
            first=second-first;
        }
        return second;
    }

    public static void main(String[] args) {
        System.out.println(fib(3));
    }
}

  4).优化4(公式)
  斐波那契数列有个线性代数解法：特征方程
package com.lg.fib;


/**
 * 斐波那契数列：1、1、2、3、5、8、13、21、34、……
 * F(1)=1，F(2)=1, F(n)=F(n-1)+F(n-2)（n≥3）
 * 编写一个函数求第 n 项斐波那契数
 */

public class FibDemo5 {

    static int fib(int n) {
        if(n <=2){ return 1;}
        return fib(n-1)+fib(n-2);
    }

    /**
     * 去除递归调用
     * @param n
     * @return
     */
    static int fib1(int n) {
        double c=Math.sqrt(5);
        return (int)((Math.pow((1+c)/2,n )-Math.pow((1-c)/2,n ))/c);
    }
    public static void main(String[] args) {
        System.out.println(fib1(3));
        System.out.println(fib(3));
    }
}

  复杂度分析：时间复杂度、空间复杂度取决于 pow 函数（至少可以低至O(logn) ）
  备注：注意并不是所有算法都有公式可以直接使用，这是个特例！！
  